package cc.lucien.demo02;

import java.util.Arrays;

/**
 * 插入排序法
 */
public class InsertionSort {
    private InsertionSort(){}

    public static <E extends Comparable<E>> void  sort(E[] arr){
        for (int i = 0; i < arr.length; i++){
            //将 arr[i]插入到合适的位置
            for (int j = i; j - 1 >= 0; j--) {
                if (arr[j].compareTo(arr[j - 1]) < 0)
                    swap(arr, j - 1, j);
                else
                    break;
            }

            //还可以这么写，但我并不喜欢，我觉得，程序的可读性很重要
//            for (int j = i; j - 1 >= 0 && (arr[j].compareTo(arr[j - 1])) < 0; j--)
//                swap(arr, j - 1, j);
        }
    }


    //优化后的插入排序算法
    public static <E extends Comparable<E>> void sort2(E[] arr) {
        for (int i = 0; i < arr.length; i++){
            //将 arr[i] 插入到合适的位置
            E temp = arr[i];
            int j;
            for (j = i; j - 1 >= 0; j--){
                if (temp.compareTo(arr[j - 1]) < 0)
                    arr[j] = arr[j - 1];
                else
                    break;
            }
            arr[j] = temp;
        }
    }

    private static <E> void swap(E[] arr, int i, int j){
        E temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int[] dataSize = {10000, 100000};
        for (int n : dataSize) {

            //对插入排序的特性进行验证，分别生成有序数组和随机数组和选择排序进行对比
            System.out.println("Random Array : ");

            Integer[] arr = ArrayGenerator.generateRandomArray(n, n);
            Integer[] arr2 = Arrays.copyOf(arr, arr.length);
            SortingHelper.sortTest("SelectionSort",arr);
            SortingHelper.sortTest("InsertionSort2", arr2);

            System.out.println();

            System.out.println("Ordered Array : ");

            arr = ArrayGenerator.generateOrderedArray(n);
            arr2 = Arrays.copyOf(arr, arr.length);
            SortingHelper.sortTest("SelectionSort",arr);
            SortingHelper.sortTest("InsertionSort2",arr2);

            System.out.println();
        }
    }
}
